混合易失和非易失主存的日志结构文件系统NOVA[FAST'16]随笔一
前言
写这篇博文的初衷是NOVA采用了Eurosys‘14文章system software for persistent memory相同的实验平台PMEP（Persistent Memory Emulation Platform）。此篇文章主要基于混合易失/非易失内存主内存上的日志结构文件系统，采用DRAM模拟的非易失内存PM（Persistent Memory），具有DAX（Direct Access）功能，可通过mmap直接将PM设备映射到应用程序地址空间中。本篇文章是我今年四月份精读过的一篇好文，所以想着要记录点什么，就写篇博文聊表心意吧。
背景
非易失内存技术
当今新型的非易失内存技术如旋转移力矩随机存取内存（STT-RAM）、相变存储器（PCM）、 电阻式随机存储器（RRAM）以及3D XPoint内存技术等，它们能够提供快速、非易失并且是字节寻址的内存。这些内存在内存层次中具有不同的优势和弱势，例如，STT-RAM的延迟能够满足或超过DRAM并且它可能最终作为处理器最后一级高速缓存使用，由于其大的单元尺寸限制了它的容量而不能够替代DRAM；PCM和ReRAM比DRAM的密度更大，可能成为大的非易失主内存，然而由于它们的相对较长的延迟使它们不能够完全替代DRAM成为主存。因特尔和美光公司主推的3D XPoint内存技术据说能够提供比NAND Flash更高的性能高达1000倍。
非易失内存软件的挑战
NVMM（Non-Volatile Main Memory）技术给文件系统设计者带来了挑战。最关键的关注点在于平衡内存性能和软件开销，强制更新的顺序性以便确保一致性并且提供原子性更新。
性能
在传统的存储系统中，低速存储设备如磁盘的延迟占了访问延迟的主要部分，所以软件效率不是关键的。然而对于快速的NVMM，软件开销很快地成为内存延迟的主导，这挥霍（squander）了NVMM能够提供的性能。 由于NVMM内存提供低延迟并驻留在处理器内存总线上，软件可以通过loads和stores来直接访问它们。当今基于NVMM的文件系统通过使用直接访问（Direct Access，简称DAX）或原地执行（eXecute In Place，简称XIP）技术来绕过DRAM页高速缓存（page cache）来直接地访问NVMM，避免了存储栈中NVMM和DRAM间额外的拷贝。NOVA就是一个DAX文件系统。
写重排序（Write Reordering）
当今处理器和它们的高速缓存层次可能对更新操作进行重排序以便提升性能。现有的模型不能够确保更新是否写入NVMM，因此当系统断电的时候会使得数据不一致。那么NVMM感知的软件通过明确地刷新高速缓存（cache）并且发送内存障碍（memory barriers）以便确保写顺序性。x86体系结构提供clflush指令以便刷新CPU cacheline，但是clflush是强一致性的，刷新成本很大并且clflush仅仅发送数据到内存控制器，并不保证数据到达非易失内存。因特尔mfence指令确保障碍前指令必须在障碍后的指令前完成。这并没有约束数据写回Memory的顺序。因此Intel公司提出了新的指令来修补这些问题，这些新指令包括clflushopt(clflust的更高效版本)，clwb(明确地写回一个缓存行而不使之无效)，以及PCOMMIT(使数据持久地存储到非易失内存中)。
原子性
POSIX类型的文件系统语义要求许多操作是原子性的，即要么全部执行要不都不执行。例如该POSIX rename操作就是原子性的，而不能出现执行和不执行的中间状态。重命名一个文件是仅对元数据进行操作，但是某些原子更新同时操作文件系统的元数据和数据。存储设备典型地只是提供初步的原子性保证，如磁盘提供原子的8字节（或更小）的扇区写。
复杂的原子操作
现有的文件系统使用各种各样的技术如journaling，shadow paging或log-structured技术来提供原子性保证。这些工作以不同的方式工作并招致了不同的开销。
journaling
Journaling又名写优先日志（write-ahead logging）被广泛地使用于journaling文件系统中和数据库中。一个journaling文件系统记录所有的更新到journal（一个固定大小的循环log）中，然后再将更新写入文件系统目标位置。在系统断电时，通过重新执行journal以便恢复系统到一致性状态。但是Journaling需要写两遍数据：一个到log一个到目标位置。为了提高性能，journaling系统经常采用只journal元数据的模式提升性能。当前工作提出了反向指针（back-pointer）和去耦合持久顺序以便减少journaling的开销。
Shadow paging
Shadow Paging属写时拷贝（Copy On Wrie，简称COW）机制。Shadow paging文件系统主要依赖于它们的树结构以便提供原子性。不是通过原地更新数据的方式，shadow paging通过写一份受影响的页的新的拷贝到存储设备新的空闲空间中。就如我们用不同的PDF阅读器打开同一个PDF时，读取时它们共享同一份数据拷贝，只有当某个阅读器编辑修改后才会形成自己新的数据拷贝，即阅读器会让你在新的文件夹位置保存该PDF文件。但是shadow paging会有一个问题，就是迭代更新的问题。
Log-structureing
日志结构文件系统（LFS）原始地设计用于利用磁盘顺序访问的高性能。LFS首先缓存随机小写到内存，再将它们转换成大的顺序写到磁盘中，大大提高了磁盘的写性能。实现日志结构文件系统复杂，原因是它需要顺序地写磁盘的连续空闲区域。日志清理增加了LFS的开销并且降低了性能。研究表明，SSDs在顺序工作负载中表现最佳。因此日志结构设计也适用于SSD。SFS、F2FS和RAMCloud均采用了日志结构存储机制。NOVA也采用了日志结构方式。
NVMM文件系统
如上图所示，显示了6种文件系统在元数据、数据和mmap原子性的特性说明情况。BPFS是一个shadow paging文件系统提供了元数据和数据的原子性。BPFS提出了硬件机制以便确保存储的持久性和顺序性，并采用了short-circuit shadow paging（SCSP）减少了shadow paging的开销。PMFS是一个轻量级的DAX文件系统绕过块层和文件系统页高速缓存（page cache）以便提高性能。PMFS使用journaling来保证元数据的更新，因此元数据原子性得到了保证。Ext4-DAX使用DAX功能扩展Ext4文件系统来直接访问NVMM，并且使用journaling技术保证元数据更新的原子性。SCMFS使用操作系统虚拟内存管理模块并且映射文件到大量连续的虚拟地址区域，使得文件访问简单，但它不提供任何元数据和数据的原子性保证。Aerie在用户空间实现了文件系统接口和功能以便提供NVMM数据的低延迟访问。而Aerie只journal 元数据而不提供数据或mmap的操作的原子性。NOVA是一个日志结构、POSIX混合易失和非易失内存文件系统，提供上述三种操作的原子性保证。
NOVA概述
NOVA是一个基于混合易失和非易失内存的日志结构、POSIX文件系统，它扩展LFS并充分利用NVMM的优势。设计NOVA基于以下三个观察。第一，日志支持原子更新容易在NVMM上实现，但是对于查找操作不高效；第二，日志清理的复杂性主要来自需要提供连续空闲的存储空间，但是在NVMM中没有必要，因为NVMM中随机访问是便宜的；第三，对于磁盘而言，使用单个日志使合理的，但是这个限制了并发性。由于NVMMs支持快速高并发随机访问，使用多个日志并不影响性能。
因此NOVA保存日志和文件数据到NVMM中，并且通过在DRAM中构建radix树结构保存索引以便加速查找操作。NOVA中每个索引结点（inode）均有自己的日志（log），允许跨文件并发更新并且无需同步化操作。该结构使得文件访问高并发，并且在故障恢复期间，可以同时重新执行多个日志。NOVA使用logging和轻量级的journaling来执行复杂的原子更新。为了原子地写数据到一个log，NOVA首先将数据追加到log，然后原子地更新该log tail指针以便提交该更新，这避免了journaling文件系统的双倍写开销以及shadow paging系统的迭代更新问题。因为NVMM支持快速并发随机访问，所以采用链表机制是可行的。因此NOVA使用4KB NVMM 页的单链表实现索引结点log。
NOVA采用非顺序日志（non-sequential log）存储，提供如下三个好处：
- 分配日志空间容易，原因是不需要分配大量的连续区域用于log；
- NOVA可以执行细粒度，页大小粒度的日志清理；
- 回收仅包含过时条目的日志页只需要几个指针分配。
NOVA中索引节点的日志不包含文件数据，相反NOVA采用写时复制技术用于修改页面（modified pages），结合追加元数据的写到日志（log）中。对于文件数据，采用写时复制（COW）原因如下：
- 这样日志可以更短，从而加快恢复过程；
- 使得垃圾回收更简单和高效，因为NOVA从不从日志中拷贝文件数据以便回收日志页（log page）；
- 回收过时页以及分配新的数据页均是简单的，因为只需要从DRAM空闲列表（free lists）中添加和移除页；
- 能够立刻回收过时的数据页，即使是在高的写负载和高NVMM使用情况下。
NOVA实现
设计混合易失和非易失内存文件系统时，Jian Xu和Steven Swanson等人面临的挑战如下：
- 实现硬件潜在的性能；
- 写重新排序和一致性的影响；
- 提供原子性操作。
NVMM数据结构和空间管理
如上图1所示是NOVA数据结构布局。NOVA将NVMM分成四个部分：超级块（superblock）和恢复结点（recovery node），journals以及日志/数据页（log/data pages)。该超级块包含文件系统的全局信息，恢复结点存储恢复信息以便加速NOVA在正常关机情况下的重新挂载（remount），索引节点表（inode tables）包含索引节点，journals提供目录操作的原子性并且剩余区域包含NVMM日志和数据页。为了获得好的扩展性，NOVA在每个CPU中保持一个索引结点表、journal和NVMM空闲页列表（free page list）以避免全局锁和扩展性瓶颈。
后续随笔二
NOVA: A Log-structured File System for Hybrid Volatile/Non-volatile Main Memories[FAST’16]，Jian Xu and Steven Swanson.
NOVA: A Log-structured File System for Hybrid Volatile/Non-volatile Main Memories[slides]
NOVA: A Log-structured file system for hybrid volatile/non-volatile main memories – Xu & Swanson 2016
